package 序列中不同最大公约数的数目;

import java.util.Arrays;

/**
 * @Program:IntelliJ IDEA
 * @description:
 * @author:香蕉你个啵娜娜 l.h-p@qq.com
 * @create:2023-01-14 20:45
 **/

public class Solution {
    // M1: 枚举所有可能的公约数 和 会产生的子序列，二者吻合的时候， ans++
    public int countDifferentSubsequenceGCDs(int[] nums){
        int maxNum = Arrays.stream(nums).max().getAsInt();
        boolean[] occured = new boolean[maxNum + 1]; // 获取数组中的最大值
        for (int num : nums){
            occured[num] = true;
        }
        int ans = 0;
        for (int i = 1; i <= maxNum; i++) { // 外循环枚举所有可能的最大公约数
            int subGcd = 0; // 初始化公约数
            for (int j = i; j <= maxNum; j+= i){
                if (occured[j]){
                    if (subGcd == 0){
                        subGcd = j;
                    }else {
                        subGcd = gcd(subGcd, j);    // 当前子序列的最大公约数
                    }
                    if (subGcd == i){
                        ans ++;
                        break;
                    }
                }
            }
        }
        return ans;
    }
    // 递归求最大公约数
    private int gcd(int a, int b){
        if (b == 0){
            return a;
        }
        return gcd(b,a%b);
    }


}
